/**
 * 
 */
package linkedlist.passed2;

/**
Sort a linked list using insertion sort.
 */
public class InsertionSortList {

	/**
	 * Definition for singly-linked list.
	 */
	 public class ListNode {
		 int val;
	     ListNode next;
	     ListNode(int x) {
	         val = x;
	         next = null;
	     }
	 }
	 
	public ListNode insertionSortList(ListNode head) {
		if (head == null || head.next == null) {
			return head;
		}
		
		final ListNode dummyNode = new ListNode(0);
		while (head != null) {
			ListNode oldHead = head;
			head = head.next;
			ListNode currNode = dummyNode;
			while (currNode.next != null) {
				if (oldHead.val > currNode.next.val || oldHead.val == currNode.next.val) {
					currNode = currNode.next;
				}
				else {
					break;
				}
			}
			ListNode next = currNode.next;
			currNode.next = oldHead;
			oldHead.next = next;
		}
		
		return dummyNode.next;
	}
	
	/**
	 * 
	 */
	public InsertionSortList() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
